#include <stdio.h>
#include <stdlib.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MAX_KEY 40001
// dp[i] = max(dp[i], dp[i-diff]+1)
int longestSubsequence(int* arr, int arrSize, int difference)
{
    int *hash = (int *)malloc(MAX_KEY * sizeof(int));
    memset(hash, 0, MAX_KEY * sizeof(int));

    int *data = (int *)malloc(arrSize * sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        data[i] = arr[i] + 20000;
    }

    int result = 0;
    for (int i = 0; i < arrSize; i++) {
        hash[data[i]] = MAX(hash[data[i]], hash[data[i] - difference] + 1);
        result = MAX(result, hash[data[i]]);
    }

    free(data);
    free(hash);
    return result;
}

void test_longestSubsequence(void)
{
    int arr[] = { 1, 5, 7, 8, 5, 3, 4, 2, 1 };
    int difference = -2;
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    printf("%d\n", longestSubsequence(arr, arrSize, difference));
}
